#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void stack_basic() {
    stack<char> s1; // 声明stack s1

    // 依次入栈 'A', 'B' 'C'
    s1.push('A');
    s1.push('B');
    s1.push('C');

    cout << "s1.size()=" << s1.size() << endl; // 求栈内元素数量

    while (!s1.empty()) { // 栈非空时, 出栈
        cout << s1.top() << endl; // 取栈顶值
        s1.pop(); // 栈顶元素出栈
    }
}

// 是否为括号
bool isBracket(char c) {
    return c == '(' || c == ')' || c == '[' || c == ']' || c == '{' || c == '}';
}

// 判断是否为"一对括号"
bool isPair(char c1, char c2) {
    if (!isBracket(c1) || !isBracket(c2)) {
        return false;
    }
    return c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}';
}

// 判断括号是否匹配
// 为说明原理, p
bool isValid(string str) {
    stack<char> s;

    for (int i = 0; i < str.size(); i++) {
        char c = str[i];
        if (s.empty()) { // 栈为空就入栈
            s.push(c);
        }

        // 是一对括号, 出栈
        // 注意这里的参数顺序
        // 因为正常的话是左括号在左边(即s.top())
        else if (isPair(s.top(), c)) {
            s.pop();
        } else if (isBracket(c)) {
            s.push(c);
        } else {
            // 不是括号, 跳过
            continue;
        }
    }

    return s.empty(); // 如果栈为空表示匹配, 否则不匹配
}

// 使用栈来模拟队列
template<typename T>
struct QueueByStack {
private:
    stack<T> in;
    stack<T> out;

public:
    void queue(T v); // 入队
    bool dequeue(T& v); // 出队
    int size(); // 大小
};

template <typename T>
void QueueByStack<T>::queue(T v) {
    in.push(v);
}

template <typename T>
bool QueueByStack<T>::dequeue(T& v) {
    if (this->out.empty()) {
        // 把in的元素弹到out中, 此时out从顶到底就是入队的顺序
        while (!this->in.empty()) {
            this->out.push(this->in.top());
            this->in.pop();
        }
    }

    if (this->out.empty()) {
        return false;
    }

    // 出队
    v = this->out.top();
    this->out.pop();
    return true;
}

template <typename T>
int QueueByStack<T>::size() {
    return this->in.size() + this->out.size();
}

// 输入两个整数序列，
// 第一个序列表示栈的压入顺序，
// 请判断第二个序列是否为该栈的弹出顺序。
// 假设压入栈的所有数字均不相等。
// 例如序列 1，2，3，4，5 是某栈的压入顺序，
// 序列 4，5，3，2，1是该压栈序列对应的一个弹出序列，
// 但4，3，5，1，2就不可能是该压栈序列的弹出序列。
// （注意：这两个序列的长度是相等的）
template <typename T>
bool isPopOrder(vector<T> pushSeq, vector<T> popSeq) {
    int n = pushSeq.size(); //
    stack<T> s;
    // i为pushSeq的索引
    // j为popSeq的索引
    for (int i = 0, j = 0; i < n; i++) {
        s.push(pushSeq[i]);

        // 如果发现s.top()和popSeq[j]相等
        // 则不断出栈
        while (j < n && !s.empty() && s.top() == popSeq[j] ) {
            s.pop();
            j++;
        }
    }
    return s.empty();
}

int main()
{
    // stack_basic();

    //
    // cout << isValid("[abc(def), {ghi}]") << endl; // 1
    // cout << isValid("{([)]}") << endl; // 0

    //
    // QueueByStack<int> qbs;
    // qbs.queue(1);
    // qbs.queue(3);
    // qbs.queue(2);
    // qbs.queue(4);

    // int i = 0;
    // // 1 3 2 4
    // while (qbs.size() > 0) {
    //     qbs.dequeue(i);
    //     cout << i << " ";
    // }
    // cout << endl;


    // vector<int>{2, 3, 4, 1, 5}这种初始化需要c++11的支持
    // 依次输出 1 0 1 1, 说明5, 4, 1, 3, 2不可能
    cout << isPopOrder<int>(vector<int>{1, 2, 3, 4, 5}, vector<int>{2, 3, 4, 1, 5}) << endl;
    cout << isPopOrder<int>(vector<int>{1, 2, 3, 4, 5}, vector<int>{5, 4, 1, 3, 2}) << endl;
    cout << isPopOrder<int>(vector<int>{1, 2, 3, 4, 5}, vector<int>{2, 3, 1, 4, 5}) << endl;
    cout << isPopOrder<int>(vector<int>{1, 2, 3, 4, 5}, vector<int>{1, 5, 4, 3, 2}) << endl;
    return 0;
}
